package main.java.sort;

import java.util.Arrays;

/**
 * @Author: 郑国荣
 * @Date: 2023-09-27-13:52
 * @Description: 希尔排序,时间复杂度O(nlogn) 空间复杂度O(1)
 * 不稳定，原地
 */
public class ShellSort {
    public int[] shellSort(int[] arr){
        int n = arr.length;
        for (int gap = n/2; gap > 0; gap/=2) { //增量从数组长度的一半开始，不断减半缩小
            for (int i = gap; i < n; i++) { //遍历每个数对
                int j = i; //临时变量
                int temp = arr[j]; //*

                while (j-gap>=0 && temp<arr[j-gap]){
                    arr[j] = arr[j-gap];
                    j-=gap;
                }
                arr[j] = temp;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        int[] arr = shellSort.shellSort(new int[]{9,8,7,6,5,4,3,2,1});
        System.out.println(Arrays.toString(arr));
    }
}
